The present invention is related to two patent applications filed on Aug. 16, 1999 entitled: xe2x80x9cMethod and Apparatus for Logic Synthesis (Word Oriented Netlist)xe2x80x9d xe2x80x9cMethod and Apparatus for Logic Synthesis (Elaboration).xe2x80x9d
The present invention pertains to the field of logic synthesis and, in particular, to method and apparatus for converting a hardware description language (xe2x80x9cHDLxe2x80x9d) model of an electronic logic system to a netlist (wherein a netlist is a data structure representation of the electronic logic system that comprises a set of modules, each of which modules comprises a data structure that specifies sub-components and their interconnection).
Automated design of application specific integrated circuits (xe2x80x9cASICxe2x80x9d) as well as programming of either programmable logic devices or programmable gate arrays requires specification of a logic circuit by a designer. A hardware description language (xe2x80x9cHDLxe2x80x9d) provides the designer with a mechanism for describing the operation of the desired logic circuit in a technology independent manner.
FIG. 1 shows a flow chart of a prior art method of logic synthesis that starts with a designer-specified HDL model of an electronic logic system and generates a Gate-Level netlist. As shown in FIG. 1, in step 100, a designer inputs a model of an electronic logic system having a desired logic functionality in the form of a set of files (HDL 10) that describe the model in a prior art HDL. As further shown in FIG. 1, in step 110, HDL 10 is parsed by a lexical analyzer and parser (lex,yacc parser 120). During parsing step 110, lex,yacc parser 120 calls routines to populate parse tree 130 (a database that is commonly referred to in the art as a parse tree). As still further shown in FIG. 1, in step 140, parse tree 130 is traversed to generate control-flow-graph 150 (CFG 150), also known in the art as a control-data-flow-graph. As yet still further shown in FIG. 1, elaboration step 160 is performed to traverse CFG 150 and populate Gate-Level Netlist 170. Gate-Level Netlist 170 is an independent and complete representation of HDL 10. It is well known to those of ordinary skill in the art how to traverse Gate-Level Netlist 170 to create a logic netlist as output.
As is well known to those of ordinary skill in the art, CFG 150 is an independent representation of the logic system (using edge and control) that is not dependent on parse tree 130 or Gate-Level Netlist 170.
In accordance with prior art logic synthesis systems, the result of elaboration step 160 is a data base, i.e., Gate-Level Netlist 170, in which each bit of a bussed net and each elaborated gate is represented by a separate data base object. Such a database is called xe2x80x9cbit-oriented.xe2x80x9d Optionally, additional objects in Gate-Level Netlist 170 track groups of bits to indicate their association as a bus object (as indicated in the HDL model). These objects are optional because the bit-oriented representation of the HDL model, while not concise, is complete. This is illustrated in FIG. 2 which shows, in schematic form, a bussed net represented in a prior art logic netlist. As shown in FIG. 2, bussed net 300 is represented by a multiplicity of individual net objects 3201, . . . , 320n and a separate bus net object 310 that associates these individual net objects into a bus.
Using such prior art netlists, it is easy to represent configurations in which bits of a bussed net behave differently because each net bit is broken into a separate object in the data base. However, due to the large number of such objects, such data bases require a large amount of computer memory. Additionally, it takes large computer runtimes to perform the prior art logic synthesis.
As one can readily appreciate from the above, a need exists in the art for a method and apparatus for logic synthesis that reduces use of computer memory and reduces computer runtime.
Embodiments of the present invention advantageously satisfy the above-identified need in the art and provide a method and apparatus for logic synthesis that reduces use of computer memory and reduces computer runtime.
In particular, an embodiment of the present invention is a method for logic synthesis which comprises the steps of: (a) analyzing an HDL model to develop a parse tree and (b) elaborating the parse tree to create a word-oriented netlist.
Aspects of the present invention include, without limitation: (a) an inventive Gate-Level netlist comprising word-oriented data objects (i.e., vector gate objects); (b) an inventive Gate Level netlist comprising novel connection objects; (c) a novel word-oriented (i.e., vector) elaboration method to create the inventive Gate-Level netlist; and (d) a novel method to infer complex components (for example, latches, flip-flops, multiplexors, and tristates) from a Gate-Level netlist (including the inventive Gate-Level netlist), without direction from the designer other than that contained within the designer-created HDL model.
In one embodiment of the present invention, novel connection objects xe2x80x9csit betweenxe2x80x9d pin and net objects to create efficiency in connections represented in xe2x80x9cGxe2x80x9d data base. Examples of such novel connection objects include: (a) full conn; (b) bit-select conn; (c) part-select conn; (d) concat conn; (e) const conn; and (f) float conn. In particular, the novel const conn object enables efficient representation of constant logic values, for example, logic0 and logic1; the novel float conn object enables efficient representation of an undriven or floating output. Further, in accordance with the present invention, a single const conn object or a single float conn object can represent an arbitrary bit-width const or float connection and, a const conn object and a float conn object can be included in a concat conn object.
In further aspects of the present invention, the inventive elaboration method utilizes the following inventive data base constructs: (a) a chunk; (b) a cache; (c) a cache item; and (d) an update item. In addition, the inventive elaboration method comprises a novel method for dealing with exceptions.
In another embodiment of the present invention, the inventive elaboration method comprises the steps of: (a) preprocessing a parse tree; (b) recursively traversing top-level statement objects in parse tree process objects; and (c) connecting net objects in the inventive word-oriented xe2x80x9cGxe2x80x9d data base. In a further embodiment of the inventive elaboration method, step (b) of recursively traversing the top-level statement objects comprises the steps of: (i) setting xe2x80x9cparentxe2x80x9d and xe2x80x9cpreviousxe2x80x9d pointers of a statement object; (ii) creating a net object and a driver object for assignment statement objects; (iii) recursing into each sub-statement object of a statement object; and (iv) propagating cache items upwards to the statement object""s xe2x80x9cparentxe2x80x9d. In a still further embodiment of the inventive elaboration method, step of (ii) of creating a net object and a driver object for assignment statement objects comprises, for an assignment statement object, the steps of (1) creating a net object in the xe2x80x9cGxe2x80x9d data base which has a bit-width equal to the width of the left-hand-side of the assignment statement object; (2) creating an update object in the xe2x80x9cVxe2x80x9d data base (the parse tree); (3) updating the cache item of the assignment statement object with the contents of the update object to provide an updated chunk list; (4) creating a xe2x80x9cfull-connxe2x80x9d object in the xe2x80x9cGxe2x80x9d data base to the net object created in the xe2x80x9cGxe2x80x9d data base in the first step; (5) carrying out a xe2x80x9cmakeConnxe2x80x9d method for the right-hand side of the assignment statement object to create conn objects; and (6) creating a buffer gate object in xe2x80x9cGxe2x80x9d data base with an output of the buffer object being set to a full-conn object created in the fourth step and an input of the buffer gate object being set to a conn object created in the fifth step. In a yet still further embodiment of the inventive elaboration method, step (iii) of connecting net objects in the inventive word-oriented xe2x80x9cGxe2x80x9d data base comprises the steps of: (1) finding a net object corresponding to the cache item""s HDL identifier; (2) creating a conn object to drive the net object; (3) carrying out a xe2x80x9cmakeConnxe2x80x9d method; and (4) creating a buffer gate object.
A further aspect of the present invention relates to a novel method for inferring complex components from a xe2x80x9cGxe2x80x9d data base. One embodiment of the present invention for inferring complex components is an inventive method for inferring latches that comprises the steps of: (a) traversing a gate netlist; (b) for a net, identifying (1) a net driver, (2) feedback connections and (3) associated enable signals that cause the feedback connections; and (c) substituting a latch gate as the driver of the net, the latch gate having (1) a data-input connected to the net driver, (2) an enable-input connected to the associated enable, and (3) a data-output to drive the net. Further steps include inserting don""t-care conditions to replace feedback connections. Another embodiment of the present invention for inferring complex components is an inventive method for inferring tristates that comprises the steps of: (a) traversing a gate netlist; (b) for a net, identifying (1) a net driver, (2) high-impedance constant connections, and (3) associated enable signals that cause the high-impedance constant connections; and (c) substituting a tristate gate as the driver of the net, the tristate gate having (1) a data-input connected to the net driver and (2) an enable-input connected to the associated enable, and (3) a data-output to drive the net. Further steps include inserting don""t-care conditions to replace high-impedance constant connections.